#ifndef __ETLMAP_H__
#define __ETLMAP_H__

#ifndef __ETL_H__
	#error etlmap.h requires etl.h to be included first
#endif

#ifndef __ETLALLOC_H__
	#error etlmap.h requires etlalloc.h to be included first
#endif

#ifndef __ETLLIST_H__
	#error etlmap.h requires etllist.h to be included first
#endif

//namespace ETL_MapHelper
//{
template <class TKey, class TVal>
PRIVATE_CLASS map_pair
{
public:
	hash_node<map_pair>* pLeft;
	hash_node<map_pair>* pRight;
	TKey first;
	TVal second;
public:
	map_pair() : pLeft(NULL), pRight(NULL){}
//	map_pair(const map_pair& src)
//	{
//		pLeft = src.pLeft;
//		pRight = src.pRight;
//		first = src.first;
//		second = src.second;
//	}
	map_pair(const TKey& _key, const TVal& _val) : pLeft(NULL), pRight(NULL), first(_key), second(_val){}
};

template <class TKey, class TVal, int rowCount = 16>
class chObjMap : protected chObjList< map_pair<TKey, TVal> , rowCount>
{
public:
	typedef map_pair<TKey, TVal>						type_map_pair;
	typedef hash_node<type_map_pair>					type_pair_node;
	typedef chObjList<type_map_pair, rowCount>			type_node_list;
	typedef hash_iterator<type_map_pair>				iterator;
public:
	iterator begin()
	{ return type_node_list::begin(); }
	iterator end()
	{ return type_node_list::end(); }
	
	// element operactor
	bool empty() const
	{ return type_node_list::empty();	}
	void clear()
	{ type_node_list::clear(); }
	void RemoveAll() // remove all alloc data
	{ type_node_list::RemoveAll(); }

	iterator erase(iterator it)
	{ return RemoveNode((*it).first); }
	void erase(const TKey& first)
	{ RemoveNode(first); }

	TVal& operator[](const TKey& first)
	{
		iterator it = find_or_alloc(first, true);
		return (*it).second;
	}
	iterator find(const TKey& first)
	{
		return find_or_alloc(first, false);
	}
private:
	iterator find_or_alloc(const TKey& first, bool bAlloc)
	{
		type_pair_node* pNode = type_node_list::m_vRootNode.vData.pLeft; // use type_node_list::m_vRootNode.vData.pLeft to store root of this tree
		if(pNode == NULL && bAlloc) // no item now
		{
			iterator it = type_node_list::AllocPushBack();
			type_node_list::m_vRootNode.vData.pLeft = it.pThisNode;
			(*it).first = first;
			return it;
		}
		while(pNode != NULL)
		{
			if(first == pNode->vData.first)
				return iterator(pNode);
			else if(first < pNode->vData.first) // find left
			{
				if(pNode->vData.pLeft == NULL && bAlloc)
				{
					iterator it = type_node_list::AllocPushBack();
					pNode->vData.pLeft = it.pThisNode;
					(*it).first = first;
					return it;
				}
				pNode = pNode->vData.pLeft;
			}
			else // find right 
			{
				if(pNode->vData.pRight == NULL && bAlloc)
				{
					iterator it = type_node_list::AllocPushBack();
					pNode->vData.pRight = it.pThisNode;
					(*it).first = first;
					return it;
				}
				pNode = pNode->vData.pRight;
			}
		}
		return type_node_list::end();
	}
	iterator RemoveNode(const TKey& first)
	{
		type_pair_node* pNode = type_node_list::m_vRootNode.vData.pLeft;
		type_pair_node** ppParentNode = &type_node_list::m_vRootNode.vData.pLeft;
		while(pNode != NULL)
		{
			if(first == pNode->vData.first)
			{ // found and remove
				UnlinkNode(ppParentNode, pNode);
				return type_node_list::erase(iterator(pNode));
			}
			if(first < pNode->vData.first) // find left
			{
				ppParentNode = &pNode->vData.pLeft;
				pNode = pNode->vData.pLeft;
			}
			else
			{
				ppParentNode = &pNode->vData.pRight;
				pNode = pNode->vData.pRight;
			}
		}
		return type_node_list::end();
	}
	void UnlinkNode(type_pair_node** ppParentNode, type_pair_node* pNode)
	{
		if(pNode->vData.pLeft == NULL && pNode->vData.pRight == NULL)
			*ppParentNode = NULL;
		else if(pNode->vData.pLeft != NULL && pNode->vData.pRight == NULL)
			*ppParentNode = pNode->vData.pLeft;
		else if(pNode->vData.pLeft == NULL && pNode->vData.pRight != NULL)
			*ppParentNode = pNode->vData.pRight;
		else
		{
			*ppParentNode = pNode->vData.pLeft;
			type_pair_node* pRightNode = pNode->vData.pRight;
			pNode = pNode->vData.pLeft;
			while(pNode != NULL)
			{
				if(pNode->vData.pRight == NULL)
				{
					pNode->vData.pRight = pRightNode;
					break;
				}
				pNode = pNode->vData.pRight;
			}
		}
	}
public:
	chObjMap() { }
	~chObjMap() { }
};

template <class TKey, class TVal, int rowCount>
class chObjMap_FixedArray
{
public:
	void erase(const TKey& key)
	{
		int i = 0;
		for(i = 0; i < rowCount; i++)
		{
			if(m_arrFlags[i] && m_arrItems[i].key == key)
			{
				m_arrFlags[i] = false;
				DestructObjects<mapItem>(m_arrItems+i, 1);
				m_nValidSize --;
				break;
			}
		}
		chASSERT(i < rowCount);
	}

	TVal& operator[](const TKey& key)
	{
		TVal* pValue = find(key);
		if(pValue == NULL)
		{
			int i;
			for(i = 0; i < rowCount; i++)
			{
				if(!m_arrFlags[i])
				{
					m_arrFlags[i] = true;
					ConstructObjects<mapItem>(m_arrItems+i, 1);
					m_nValidSize ++;
					m_arrItems[i].key = key;
					pValue = &m_arrItems[i].value;
					break;
				}
			}
			chASSERT(i < rowCount);
		}
		return *pValue;
	}
	TVal* find(const TKey& key)
	{
		int i;
		for(i = 0; i < rowCount; i++)
		{
			if(m_arrFlags[i] && m_arrItems[i].key == key)
			{
				return &m_arrItems[i].value;
			}
		}
		return NULL;
	}
public:
	chObjMap_FixedArray() : m_nValidSize(0)
	{
		m_arrItems = (mapItem*)malloc(sizeof(mapItem) * rowCount);
		int i;
		for(i = 0; i < rowCount; i++)
			m_arrFlags[i] = false;
	}
	~chObjMap_FixedArray()
	{
		int i;
		for(i = 0; i < rowCount; i++)
		{
			if(m_arrFlags[i])
			{
				m_arrFlags[i] = false;
				DestructObjects<mapItem>(m_arrItems+i, 1);
				m_nValidSize --;
			}
		}
		free(m_arrItems);
	}
private:
	struct mapItem
	{
		TKey key;
		TVal value;
	};
	mapItem*			m_arrItems;
	bool				m_arrFlags[rowCount];
	int					m_nValidSize;
};

//};
//using namespace ETL_MapHelper;

#endif //__ETLMAP_H__
